'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-04-17 10:44:08
'''
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        import queue
        store = queue.Queue()
        store.put(0)
        test = [False]*len(nums)
        test[0] = True
        # print(test)
        while not store.empty():
            tmp = store.get()
            l = nums[tmp]
            # print(tmp, l)

            for i in range(1, l+1):
                if tmp+i<len(nums) and not test[tmp+i]:
                    if tmp+i == len(nums) - 1:
                        return True
                    store.put(tmp+i)
                    test[tmp+i] = True
                elif tmp+i>=len(nums):
                    break
        # print(test)
        return False
if __name__ == "__main__":
    s = Solution()
    nums = [8,2,4,4,4,9,5,2,5,8,8,0,8,6,9,1,1,6,3,5,1,2,6,6,0,4,8,6,0,3,2,8,7,6,5,1,7,0,3,4,8,3,5,9,0,4,0,1,0,5,9,2,0,7,0,2,1,0,8,2,5,1,2,3,9,7,4,7,0,0,1,8,5,6,7,5,1,9,9,3,5,0,7,5]
    # print(nums[24])
    # print(len(nums))
    print(s.canJump(nums))